package com.zhanghp.class034;

import com.zhanghp.common.ListNode;

/**
 * 判断链表是否是回文结构<br/>
 * 测试链接 : https://leetcode.cn/problems/palindrome-linked-list/<br/>
 * <ul>
 *     <li>
 *         利用slow，fast指针，找到中点
 *     </li>
 *     <li>
 *         从中点处，反转中点往后的连接的节点<br/>
 *         a->b-> c <-b<-a (c此时指向的是null)<br/>
 *     </li>
 *     <li>
 *         对比
 *     </li>
 *     <li>
 *         将反转后的节点恢复原样：a->b->c->b->a
 *     </li>
 * </ul>
 *
 * @author zhanghp
 * @since 2024/4/11 9:56
 */
public class Code04_PalindromeLinkedList {

    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(2);
        ListNode e = new ListNode(1);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        System.out.println(new Solution().isPalindrome(a));

    }
    static class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null ) {
                return true;
            }
            // 寻找中点（对称轴）
            ListNode slow = head, fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            // 反转 slow.next -> ...
            // a -> b -> c <- b < -a
            ListNode n = slow.next;
            ListNode pre = reverse(slow.next);
            slow.next = null;
            n.next = slow;

            // 对比
            ListNode left = head, right = pre;
            boolean ans = true;
            while (left != null && right != null) {
                if (left.val != right.val) {
                    ans  = false;
                    break;
                }
                left = left.next;
                right = right.next;
            }
            // 还原head链表
            // reverse(pre).next 原因
            // 上面反转时，将最后的尾节点的下一个连的slow节点
            // 所以这个地方反转，去除slow节点
            slow.next =  reverse(pre).next;
            return ans;
        }

        public ListNode reverse(ListNode node){
            ListNode pre = null,  cur = node, temp;
            while (cur != null) {
                temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
            return pre;
        }
    }

    static class ZuoSolution{
        public static boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null) {
                return true;
            }
            ListNode slow = head, fast = head;
            // 找中点
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            // 现在中点就是slow，从中点开始往后的节点逆序
            ListNode pre = slow;
            ListNode cur = pre.next;
            ListNode next = null;
            pre.next = null;
            while (cur != null) {
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            // 上面的过程已经把链表调整成从左右两侧往中间指
            // head -> ... -> slow <- ... <- pre
            boolean ans = true;
            ListNode left = head;
            ListNode right = pre;
            // left往右、right往左，每一步比对值是否一样，如果某一步不一样答案就是false
            while (left != null && right != null) {
                if (left.val != right.val) {
                    ans = false;
                    break;
                }
                left = left.next;
                right = right.next;
            }
            // 本着不坑的原则，把链表调整回原来的样子再返回判断结果
            cur = pre.next;
            pre.next = null;
            next = null;
            while (cur != null) {
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return ans;
        }
    }
}
